package main

func heapify(nums []int, i int, heapSize int) {
	left := 2*i + 1
	right := 2*i + 2
	largest := i
	if left < heapSize && nums[left] > nums[largest] {
		largest = left
	}
	if right < heapSize && nums[right] > nums[largest] {
		largest = right
	}
	if i != largest {
		nums[i], nums[largest] = nums[largest], nums[i]
		heapify(nums, largest, heapSize)
	}
}


func findKthLargest(nums []int, k int) int {
	heapSize := len(nums)
	for i := heapSize/2; i >= 0; i-- {
		heapify(nums, i, heapSize)
	}
	for i := 0; i < k - 1; i++ {
		j := heapSize - 1
		nums[j], nums[0] = nums[0], nums[j]
		heapSize--
		heapify(nums, 0, heapSize)
	}
	return nums[0]
}

func main() {
	println(findKthLargest([]int{3, 2, 1, 5, 6, 4}, 2))
}
